# storage_system.py
"""
简化版数据库存储系统（单文件实现）
功能：
  - 页式存储（4KB/页）
  - 页分配、释放、读写
  - 表映射到页集合
  - 缓存管理（LRU/FIFO）
  - 缓存命中统计与替换日志
  - 内置测试演示
"""

import os
import json
import time
from collections import deque
from typing import Dict, List, Optional, Any, Union

# ==================== 配置 ====================
PAGE_SIZE = 4096          # 每页 4KB
DEFAULT_DB_PATH = "db_file.dat"
CACHE_SIZE = 10           # 缓存池最多缓存 10 页
REPLACE_STRATEGY = "LRU"  # 可选: "LRU" 或 "FIFO"


# ==================== 工具函数 ====================
def generate_uuid() -> str:
    """简单模拟 UUID 生成"""
    return str(abs(hash(str(time.time()) + str(os.getpid()))) % (10 ** 16))


# ==================== 1. 页对象 ====================
class Page:
    """内存中的页对象"""
    def __init__(self, page_id: int):
        self.page_id = page_id
        self.data = bytearray(PAGE_SIZE)
        self.is_dirty = False
        self.is_valid = False  # 是否已写入数据
        self.last_access = time.time()

    def read(self) -> bytes:
        """读取整页数据"""
        if not self.is_valid:
            raise ValueError(f"Page {self.page_id} has not been initialized.")
        return bytes(self.data)

    def write(self, data: bytes) -> None:
        """写入数据到页"""
        if len(data) > PAGE_SIZE:
            raise ValueError(f"Data size {len(data)} exceeds page size {PAGE_SIZE}")
        self.data[:len(data)] = data
        self.data[len(data):] = b'\x00' * (PAGE_SIZE - len(data))
        self.is_valid = True
        self.is_dirty = True
        self.last_access = time.time()

    def __repr__(self):
        return f"<Page id={self.page_id}, dirty={self.is_dirty}, valid={self.is_valid}>"


# ==================== 2. 磁盘模拟器 ====================
class DiskManager:
    """模拟磁盘读写"""
    def __init__(self, file_path: str):
        self.file_path = file_path
        self.page_size = PAGE_SIZE
        self._ensure_file()

    def _ensure_file(self):
        """确保文件存在且大小为页对齐"""
        if not os.path.exists(self.file_path):
            with open(self.file_path, 'wb') as f:
                f.write(b'\x00' * self.page_size)
        size = os.path.getsize(self.file_path)
        if size % self.page_size != 0:
            with open(self.file_path, 'ab') as f:
                pad = self.page_size - (size % self.page_size)
                f.write(b'\x00' * pad)

    def read_page(self, page_id: int) -> bytes:
        """从磁盘读一页"""
        offset = page_id * self.page_size
        with open(self.file_path, 'rb') as f:
            f.seek(offset)
            data = f.read(self.page_size)
            if len(data) < self.page_size:
                data += b'\x00' * (self.page_size - len(data))
            return data

    def write_page(self, page_id: int, data: bytes) -> None:
        """写一页到磁盘"""
        assert len(data) == self.page_size, "Data must be exactly one page size"
        offset = page_id * self.page_size
        with open(self.file_path, 'r+b') as f:
            f.seek(offset)
            f.write(data)
        # 扩展文件
        f_size = os.path.getsize(self.file_path)
        if offset + self.page_size > f_size:
            f.seek(0, 2)
            pad = offset + self.page_size - f_size
            f.write(b'\x00' * pad)

    def get_num_pages(self) -> int:
        """获取总页数"""
        return os.path.getsize(self.file_path) // self.page_size


# ==================== 3. 缓存管理器 ====================
class BufferPool:
    """缓存池，支持 LRU 和 FIFO 替换策略"""
    def __init__(self, max_pages: int, strategy: str = "LRU"):
        self.max_pages = max_pages
        self.strategy = strategy.upper()
        assert self.strategy in ("LRU", "FIFO"), "Strategy must be LRU or FIFO"
        self.pages: Dict[int, Page] = {}  # page_id -> Page
        self.access_log: deque = deque()  # 用于记录访问顺序
        self.hit_count = 0
        self.access_count = 0
        self.replace_log: List[str] = []

    def _evict(self) -> int:
        """淘汰一页，返回被淘汰的 page_id"""
        if len(self.pages) < self.max_pages:
            return -1

        if self.strategy == "LRU":
            # 找最久未使用的：访问日志中最先出现的
            victim = None
            for pid in self.access_log:
                if pid in self.pages:
                    victim = pid
                    break
            if victim is None:
                victim = next(iter(self.pages))
        else:  # FIFO
            victim = self.access_log[0] if self.access_log else next(iter(self.pages))

        page = self.pages[victim]
        log_entry = f"[{time.strftime('%H:%M:%S')}] Evicted page {victim} (dirty={page.is_dirty})"
        self.replace_log.append(log_entry)
        print(log_entry)

        if page.is_dirty:
            print(f"  → Flushing dirty page {victim} to disk...")
            # 实际写回由外部完成，这里只记录

        del self.pages[victim]
        # 清理日志中的旧记录
        self.access_log = deque([pid for pid in self.access_log if pid != victim])
        return victim

    def get_page(self, page_id: int) -> Page:
        """获取页（命中则返回，未命中则模拟加载）"""
        self.access_count += 1
        if page_id in self.pages:
            self.hit_count += 1
            self.access_log.append(page_id)
            self.pages[page_id].last_access = time.time()
            return self.pages[page_id]

        # 未命中，需加载（模拟）
        while len(self.pages) >= self.max_pages:
            self._evict()

        new_page = Page(page_id)
        self.pages[page_id] = new_page
        self.access_log.append(page_id)
        print(f"Loaded page {page_id} into buffer pool.")
        return new_page

    def flush_page(self, page_id: int) -> bool:
        """将指定页写回磁盘（如果脏）"""
        if page_id not in self.pages:
            return False
        page = self.pages[page_id]
        if page.is_dirty and page.is_valid:
            print(f"Flushing page {page_id} to disk...")
            # 实际写回由 StorageManager 完成
            page.is_dirty = False
            return True
        return False

    def flush_all(self):
        """刷新所有脏页"""
        for pid in list(self.pages.keys()):
            self.flush_page(pid)

    def is_in_pool(self, page_id: int) -> bool:
        return page_id in self.pages

    def get_stats(self) -> Dict[str, Any]:
        hit_rate = self.hit_count / self.access_count if self.access_count > 0 else 0
        return {
            "hit_count": self.hit_count,
            "access_count": self.access_count,
            "hit_rate": round(hit_rate, 4),
            "pool_size": len(self.pages),
            "max_size": self.max_pages,
            "strategy": self.strategy,
            "replace_log_count": len(self.replace_log)
        }

    def print_stats(self):
        stats = self.get_stats()
        print(f"\n=== 缓存统计 ===")
        print(f"命中率: {stats['hit_rate']:.2%} ({stats['hit_count']}/{stats['access_count']})")
        print(f"缓存使用: {stats['pool_size']}/{stats['max_size']} 页")
        print(f"替换策略: {stats['strategy']}")

    def print_replace_log(self):
        print(f"\n=== 替换日志（最近10条）===")
        for log in self.replace_log[-10:]:
            print(log)


# ==================== 4. 表映射管理器 ====================
class TableMapper:
    """将数据表映射到页集合"""
    METADATA_PAGE_ID = 0

    def __init__(self, disk: DiskManager):
        self.disk = disk
        self.tables: Dict[str, List[int]] = {}
        self.next_page_id = 1  # 0号页留给元数据
        self.load_metadata()

    def load_metadata(self):
        """从磁盘加载元数据"""
        try:
            data = self.disk.read_page(self.METADATA_PAGE_ID)
            meta_str = data.split(b'\x00')[0].decode('utf-8', errors='ignore')
            if meta_str.strip():
                meta = json.loads(meta_str)
                self.tables = meta.get("tables", {})
                self.next_page_id = meta.get("next_page_id", 1)
        except Exception as e:
            print(f"Warning: failed to load metadata, initializing new. Error: {e}")
            self.tables = {}
            self.next_page_id = 1

    def flush_metadata(self):
        """将元数据写回磁盘"""
        meta = {
            "tables": self.tables,
            "next_page_id": self.next_page_id,
            "timestamp": time.time()
        }
        meta_bytes = json.dumps(meta, ensure_ascii=False).encode('utf-8')
        if len(meta_bytes) > PAGE_SIZE:
            raise RuntimeError("Metadata too large for one page")
        data = bytearray(PAGE_SIZE)
        data[:len(meta_bytes)] = meta_bytes
        self.disk.write_page(self.METADATA_PAGE_ID, data)

    def create_table(self, table_name: str, num_pages: int = 1):
        """创建表并分配页"""
        if table_name in self.tables:
            raise ValueError(f"Table '{table_name}' already exists.")
        page_ids = []
        for _ in range(num_pages):
            page_ids.append(self.allocate_page())
        self.tables[table_name] = page_ids
        self.flush_metadata()
        print(f"✅ 表 '{table_name}' 创建成功，分配 {num_pages} 页。")

    def drop_table(self, table_name: str):
        """删除表"""
        if table_name not in self.tables:
            raise ValueError(f"表 '{table_name}' 不存在。")
        del self.tables[table_name]
        self.flush_metadata()
        print(f"🗑️ 表 '{table_name}' 已删除。")

    def get_table_pages(self, table_name: str) -> List[int]:
        """获取表的页ID列表"""
        if table_name not in self.tables:
            raise ValueError(f"表 '{table_name}' 不存在。")
        return self.tables[table_name]

    def allocate_page(self) -> int:
        """分配新页ID"""
        page_id = self.next_page_id
        self.next_page_id += 1
        # 扩展文件
        current_pages = self.disk.get_num_pages()
        if page_id >= current_pages:
            with open(self.disk.file_path, 'ab') as f:
                f.write(b'\x00' * PAGE_SIZE)
        return page_id

    def free_page(self, page_id: int):
        """释放页（简化：不真正回收）"""
        pass


# ==================== 5. 存储管理器（主接口）====================
class StorageManager:
    """统一的存储访问接口"""
    def __init__(self, db_path: str = DEFAULT_DB_PATH, cache_size: int = CACHE_SIZE, strategy: str = REPLACE_STRATEGY):
        self.db_path = db_path
        self.disk = DiskManager(db_path)
        self.buffer_pool = BufferPool(cache_size, strategy)
        self.table_mapper = TableMapper(self.disk)
        self.is_open = False

    def open(self):
        """启动存储系统"""
        if self.is_open:
            return
        print(f"🚀 启动存储系统: {self.db_path}")
        self.is_open = True

    def close(self):
        """关闭存储系统"""
        if not self.is_open:
            return
        self.buffer_pool.flush_all()
        self.table_mapper.flush_metadata()
        self.is_open = False
        print("💾 存储系统已关闭。")

    def read_page(self, page_id: int) -> bytes:
        """直接读页（绕过缓存）"""
        return self.disk.read_page(page_id)

    def write_page(self, page_id: int, data: bytes):
        """直接写页（绕过缓存）"""
        if len(data) != PAGE_SIZE:
            raise ValueError("数据必须恰好一页大小")
        self.disk.write_page(page_id, data)

    def get_page(self, page_id: int) -> Page:
        """获取页（走缓存）"""
        return self.buffer_pool.get_page(page_id)

    def flush_page(self, page_id: int):
        """刷新指定页"""
        self.buffer_pool.flush_page(page_id)
        data = self.get_page(page_id).read()
        self.write_page(page_id, data)

    def create_table(self, name: str, pages: int = 1):
        self.table_mapper.create_table(name, pages)

    def drop_table(self, name: str):
        self.table_mapper.drop_table(name)

    def insert_data(self, table_name: str, data: Any):
        """插入数据（简化：只写第一页）"""
        import pickle
        page_ids = self.table_mapper.get_table_pages(table_name)
        page = self.get_page(page_ids[0])
        serialized = pickle.dumps(data)
        page.write(serialized)

    def read_data(self, table_name: str) -> Any:
        """读取数据"""
        import pickle
        page_ids = self.table_mapper.get_table_pages(table_name)
        page = self.get_page(page_ids[0])
        data = page.read()
        try:
            return pickle.loads(data.strip(b'\x00'))
        except:
            return data


# ==================== 6. 内置测试函数 ====================
def test_lru_vs_fifo():
    """对比 LRU 和 FIFO 的页面淘汰顺序"""
    print("🧪 测试：LRU vs FIFO 替换策略差异\n")

    def simulate_access(strategy: str, access_seq: list):
        print(f"\n👉 使用 {strategy} 策略，访问序列: {access_seq}")
        sm = StorageManager(f"{strategy.lower()}_test.db", cache_size=3, strategy=strategy)
        sm.open()

        for pid in access_seq:
            sm.get_page(pid)
            time.sleep(0.01)  # 防止时间戳相同

        sm.buffer_pool.print_stats()
        sm.buffer_pool.print_replace_log()
        sm.close()

    # 访问序列：1→2→3→1→4 → 期望：FIFO 淘汰 1，LRU 淘汰 2
    seq = [1, 2, 3, 1, 4]

    simulate_access("LRU", seq)
    simulate_access("FIFO", seq)



# ==================== 主程序入口 ====================
if __name__ == '__main__':
   
    test_lru_vs_fifo()